package com.atguigu.exercise;

/**
 * @author RuiKnag
 * @create 2021-05-24-16:26
 */
public class Cal {
    public static void main(String[] args) {
        String s="ababab";
        String t="abababab";
        int i = kmp(s, t);
        System.out.println("i = " + i);
    }
    public static int kmp (String S, String T) {
        // write code here
        int[] next=kmpNext(S);
        int res=0;
        for(int i=0,j=0;i<T.length();i++){
            while(j>0&&T.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            if(S.charAt(j)==T.charAt(i)){
                j++;
            }
            if(j==S.length()){
                i=(i-j+1);
                j=0;
                res++;
            }
        }
        return res;
    }
    public static int[] kmpNext(String S){
        int[][] res1=new int[3][];
        for (int i = 0; i < res1.length; i++) {
            for (int j = 0; j <3; j++) {
                res1[i][j]=j;
            }

        }
        System.out.println(res1.toString());
        int[] res=new int[S.length()];
        res[0]=0;
        for(int i=1,j=0;i<S.length();i++){
            while(j>0&&S.charAt(i)!=S.charAt(j)){
                j=res[j-1];
            }
            if(S.charAt(i)==S.charAt(j)){
                j++;
            }
            res[i]=j;
        }
        return res;
    }
}